/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode LTNode;  
int GetLength(LTNode* root)
{
    int cnt = 0;
    while (root)
    {
        cnt++;
        root = root->next;
    }
    return cnt;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    int len1 = GetLength(l1);
    int len2 = GetLength(l2);
    int sub = len1 > len2 ? len1-len2 : len2-len1;
    LTNode* max = l1;
    LTNode* min = l2;
    if (len1 < len2)
    {
        max = l2;
        min = l1;
    }
    LTNode* head = NULL;
    while (sub--)
    {
        LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
        newNode->val = max->val;
        newNode->next = NULL;   
        newNode->next = head;
        max = max->next;
        head = newNode;     
    }
    while (max)
    {
        LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
        newNode->val = (max->val + min->val);
        newNode->next = NULL;   
        newNode->next = head;
        head = newNode;
        max = max->next;
        min = min->next;
    }   

    LTNode* cur = head;
    LTNode* pre = NULL;
    int flg = 0;
    while (cur)
    {
        pre = cur;
        cur->val += flg;
        flg = cur->val >= 10 ? 1 : 0;
        cur->val %= 10;
        cur = cur->next;
    }
    if (flg)
    {
        cur = (LTNode*)malloc(sizeof(LTNode));
        cur->val = flg;
        cur->next = NULL;  
        pre->next = cur; 
    }
    LTNode* n1 = NULL;
    LTNode* n2 = head;
    while (n2)
    {
        LTNode* n3 = n2->next;
        n2->next = n1;
        n1 = n2;
        n2 = n3;
    }
    return n1;
}